翻訳と辞書 Words near each other ・ Quantum superposition ・ Quantum system ・ Quantum t-design ・ Quantum technology ・ Quantum teleportation ・ Quantum field theory ・ Quantum field theory in curved spacetime ・ Quantum finance ・ Quantum fingerprinting ・ Quantum finite automata ・ Quantum Fireball ・ Quantum fluctuation ・ Quantum fluid ・ Quantum flux parametron ・ Quantum foam ・ Quantum Fourier transform ・ Quantum game theory ・ Quantum gate ・ Quantum Gate (video game) ・ Quantum gauge theory ・ Quantum geometry ・ Quantum graph ・ Quantum gravity ・ Quantum group ・ Quantum Group of Funds ・ Quantum Guitar ・ Quantum gyroscope ・ Quantum Hall effect ・ Quantum Hall transitions ・ Quantum harmonic oscillator Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Quantum Fourier transform ： ウィキペディア英語版 Quantum Fourier transform In quantum computing, the quantum Fourier transform is a linear transformation on quantum bits, and is the quantum analogue of the discrete Fourier transform. The quantum Fourier transform is a part of many quantum algorithms, notably Shor's algorithm for factoring and computing the discrete logarithm, the quantum phase estimation algorithm for estimating the eigenvalues of a unitary operator, and algorithms for the hidden subgroup problem. The quantum Fourier transform can be performed efficiently on a quantum computer, with a particular decomposition into a product of simpler unitary matrices. Using a simple decomposition, the discrete Fourier transform on $2^n$ amplitudes can be implemented as a quantum circuit consisting of only $O(n^2)$ Hadamard gates and controlled phase shift gates, where $n$ is the number of qubits. This can be compared with the classical discrete Fourier transform, which takes $O(n2^n)$ gates (where $n$ is the number of bits), which is exponentially more than $O(n^2)$. However, the quantum Fourier transform acts on a quantum state, whereas the classical Fourier transform acts on a vector, so not every task that uses the classical Fourier transform can take advantage of this exponential speedup. The best quantum Fourier transform algorithms known today require only $O(n\; \backslash log\; n)$ gates to achieve an efficient approximation.〔L. Hales, S. Hallgren, An improved quantum Fourier transform algorithm and applications, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p. 515, November 12–14, 2000〕 == Definition == The quantum Fourier transform is the classical discrete Fourier transform applied to the vector of amplitudes of a quantum state. The classical (unitary) Fourier transform acts on a vector in $\backslash mathbb^N$, (''x''0, ..., ''x''''N''−1) and maps it to the vector (''y''0, ..., ''y''''N''−1) according to the formula: :$y\_k\; =\; \backslash frac^\; x\_j\; \backslash omega^$ where $\backslash omega^\; =\; e^\}$ is a ''N''th root of unity. Similarly, the quantum Fourier transform acts on a quantum state $\backslash sum\_^\; x\_i\; |i\backslash rangle$ and maps it to a quantum state $\backslash sum\_^\; y\_i\; |i\backslash rangle$ according to the formula: :$y\_k\; =\; \backslash frac^\; x\_j\; \backslash omega^,$ with $\backslash omega^$ defined as above. This can also be expressed as the map :$|j\backslash rangle\; \backslash mapsto\; \backslash frac^\; \backslash omega^\; |k\backslash rangle.$ Equivalently, the quantum Fourier transform can be viewed as a unitary matrix (quantum gate, similar to a logic gate for classical computers) acting on quantum state vectors, where the unitary matrix $F\_N$ is given by :$$ F_N = \frac 1&1&1&1&\cdots &1 \\ 1&\omega&\omega^2&\omega^3&\cdots&\omega^ \\ 1&\omega^2&\omega^4&\omega^6&\cdots&\omega^\\ 1&\omega^3&\omega^6&\omega^9&\cdots&\omega^\\ \vdots&\vdots&\vdots&\vdots&&\vdots\\ 1&\omega^&\omega^&\omega^&\cdots&\omega^ \end. Here $\backslash omega\; =\; e^\}$ is a primitive ''N''th root of unity. For example, in the case of $N=4$ we would find that $\backslash omega\; =\; i$, so :$$ F_4 = \frac \begin 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Quantum Fourier transform」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.